package week7;

import jsjf.exceptions.*;
import week6.BinaryTreeNode;

public class LinkedAVLTree<T> extends LinkedBinarySearchTree<T>{
    public LinkedAVLTree() {
        root = null;
    }

    public LinkedAVLTree(T element) {
        root = new BinaryTreeNode<T>(element);
    }

    public BinaryTreeNode<T> getRootNode() throws EmptyCollectionException{
        if (isEmpty()) {
            throw new EmptyCollectionException("AVLTreeNode ");
        }
        return root;
    }

//    private int calHeight(BinaryTreeNode<T> node) {
//        if (node == null) {
//            return 0;
//        }
//        int leftHeight = node.left == null ? 0 : node.left.height;
//        int rightHeight = node.right == null ? 0 : node.right.height;
//        return Math.max(leftHeight, rightHeight) + 1;
//    }

    public int getHeight(BinaryTreeNode<T> node)
    {
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        return Math.max(leftHeight, rightHeight);
    }
    public boolean isEmpty()
    {
        return (root == null);
    }

    public BinaryTreeNode<T> rightRotation(BinaryTreeNode<T> node)
    {
        BinaryTreeNode<T> node1;

//        node1 = node.left;
//        node1.right = node;
//        node.left = node1.right;


         node1 = node.left;
         node.left = node1.right;
         node1.right = node;

        node.height = Math.max(height(node.left),height(node.right));
        node1.height = Math.max(height(node1.left),height(node1.right));
        return node1;
    }

    public BinaryTreeNode<T> leftRotation(BinaryTreeNode<T> node)
    {
        BinaryTreeNode<T> node1;

        node1 = node.right;
        node.right = node1.left;
        node1.left = node;

        node.height = Math.max(height(node.left),height(node.right));
        node1.height = Math.max(height(node1.left),height(node1.right));
        return node1;
    }

    public BinaryTreeNode<T> rightLeftRotation(BinaryTreeNode<T> node)
    {
        BinaryTreeNode<T> node1;

        node.left = rightRotation(node.left);
        node1 = leftRotation(node);

        return node1;
    }

    public BinaryTreeNode<T> leftRightRotation(BinaryTreeNode<T> node)
    {
        BinaryTreeNode<T> node1;

        node.right = rightRotation(node.right);
        node1 = rightRotation(node);

        return node1;
    }

    public void addElement(T element) {

        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedAVLTree");

        Comparable<T> comparableElement = (Comparable<T>) element;

//        root.height = getHeight(root);
        if (isEmpty()) {
            root = new BinaryTreeNode<T>(element);
        } else {
            if (comparableElement.compareTo(root.getElement()) < 0) {
                if (root.getLeft() == null)
                    this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
                else
                    addElement(element, root.getLeft());
                if (!isBalanced(root)) {
                    if (comparableElement.compareTo(root.left.getElement()) < 0) {
                        root = rightRotation(root);   // 右旋
                    } else {
                        root = leftRightRotation(root);     // 左右旋
                    }
                }

            } else {
                if (root.getRight() == null)
                    this.getRootNode().setRight(new BinaryTreeNode<T>(element));
                else
                    addElement(element, root.getRight());
                if (!isBalanced(root)) {
                    if (comparableElement.compareTo(root.right.getElement()) > 0) {
                        root = leftRotation(root);     // 左旋
                    } else {
                        root = rightLeftRotation(root);     // 右左旋
                    }
                }
            }
        }
    }

    private void addElement(T element, BinaryTreeNode<T> node)
    {
        Comparable<T> comparableElement = (Comparable<T>)element;

        if (comparableElement.compareTo(node.getElement()) < 0)
        {
            if (node.getLeft() == null)
                node.setLeft(new BinaryTreeNode<>(element));
            else
                addElement(element, node.getLeft());
        }
        else
        {
            if (node.getRight() == null)
                node.setRight(new BinaryTreeNode<>(element));
            else
                addElement(element, node.getRight());
        }
    }

    // 删除
    public T removeElement(T targetElement) throws ElementNotFoundException
    {
        T result = null;

        if (isEmpty())
            throw new ElementNotFoundException("LinkedAVLTree");
        else
        {
            BinaryTreeNode<T> parent = null;
            // 删除根结点
            if (((Comparable<T>)targetElement).equals(root.element))
            {
                result =  root.element;
                BinaryTreeNode<T> temp = replacement(root);
                if (temp == null)
                    root = null;
                else
                {
                    root.element = temp.element;
                    root.setRight(temp.right);
                    root.setLeft(temp.left);
                    if (!isBalanced(root))
                    {

                    }
                }
            }
            else
            {
                parent = root;
                if (((Comparable)targetElement).compareTo(root.element) < 0)
                    result = removeElement(targetElement, root.getLeft(), parent);
                else
                    result = removeElement(targetElement, root.getRight(), parent);
            }
        }

        return result;
    }

    private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent)
            throws ElementNotFoundException
    {
        T result = null;

        if (node == null)
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else
        {
            if (((Comparable<T>)targetElement).equals(node.element))
            {
                result =  node.element;
                BinaryTreeNode<T> temp = replacement(node);
                if (parent.right == node)
                    parent.right = temp;
                else
                    parent.left = temp;

            }
            else
            {
                parent = node;
                if (((Comparable)targetElement).compareTo(node.element) < 0)
                    result = removeElement(targetElement, node.getLeft(), parent);
                else
                    result = removeElement(targetElement, node.getRight(), parent);
            }
        }

        return result;
    }

    // 返回对节点的引用，该节点将替换指定要删除的节点。
    // 在删除的节点有两个子节点的情况下，将使用中序继承节点作为其替代节点。
    private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node)
    {
        BinaryTreeNode<T> result = null;

        if ((node.left == null) && (node.right == null))
            result = null;

        else if ((node.left != null) && (node.right == null))
            result = node.left;

        else if ((node.left == null) && (node.right != null))
            result = node.right;

        else
        {
            BinaryTreeNode<T> current = node.right;
            BinaryTreeNode<T> parent = node;

            while (current.left != null)
            {
                parent = current;
                current = current.left;
            }

            current.left = node.left;
            if (node.right != current)
            {
                parent.left = current.right;
                current.right = node.right;
            }

            result = current;
        }

        return result;
    }

    public String toString()
    {
        return super.toString();
    }

    // 判断以该结点为树根的子树是否需要平衡
    public boolean isBalanced(BinaryTreeNode<T> node) {
        int leftHeight = 0;
        if (node.left != null)
        {
            leftHeight = getHeight(node.left);
        }

        int rightHeight = 0;
        if (node.right != null)
        {
            rightHeight = getHeight(node.right);
        }

        return Math.abs(leftHeight - rightHeight) <= 1;
    }
}
